{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Split Array with Equal Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: splitArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #将数组分割成和相等的子数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个有 <code>n</code> 个整数的数组 <code>nums</code>&nbsp;，如果能找到满足以下条件的三元组&nbsp; <code>(i, j, k)</code>&nbsp; 则返回 <code>true</code> ：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li><code>0 &lt; i, i + 1 &lt; j, j + 1 &lt; k &lt; n - 1</code></li>\n",
    "\t<li>子数组 <code>(0, i - 1)</code>&nbsp;， <code>(i + 1, j - 1)</code> ， <code>(j + 1, k - 1)</code> ， <code>(k + 1, n - 1)</code> 的和应该相等。</li>\n",
    "</ol>\n",
    "\n",
    "<p>这里我们定义子数组&nbsp;<code>(l, r)</code>&nbsp;表示原数组从索引为&nbsp;<code>l</code>&nbsp;的元素开始至索引为&nbsp;<code>r</code> 的元素。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:&nbsp;</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [1,2,1,2,1,2,1]\n",
    "<strong>输出:</strong> True\n",
    "<strong>解释:</strong>\n",
    "i = 1, j = 3, k = 5. \n",
    "sum(0, i - 1) = sum(0, 0) = 1\n",
    "sum(i + 1, j - 1) = sum(2, 2) = 1\n",
    "sum(j + 1, k - 1) = sum(4, 4) = 1\n",
    "sum(k + 1, n - 1) = sum(6, 6) = 1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [1,2,1,2,1,2,1,2]\n",
    "<strong>输出:</strong> false\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n ==&nbsp;nums.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 2000</code></li>\n",
    "\t<li><code>-10<sup>6</sup>&nbsp;&lt;= nums[i] &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [split-array-with-equal-sum](https://leetcode.cn/problems/split-array-with-equal-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [split-array-with-equal-sum](https://leetcode.cn/problems/split-array-with-equal-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,1,2,1,2,1]', '[1,2,1,2,1,2,1,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        sub = [0] + nums\n",
    "        for j in range(2, n + 1):\n",
    "            sub[j] += sub[j-1]\n",
    "        # k * n\n",
    "        dp = [[0] * n] * k\n",
    "        for j in range(n):\n",
    "            dp[0][j] = sub[-1] - sub[j]\n",
    "        \n",
    "        for i in range(1, k):\n",
    "            for j in range(n-i):\n",
    "                curr_min = float(\"inf\")\n",
    "                for c in range(j + 1, n):\n",
    "                    left_sum = sub[c] - sub[j]\n",
    "                    curr_min = min(curr_min, max(left_sum, dp[i-1][c]))\n",
    "                    if left_sum >= dp[i-1][c]:\n",
    "                        break\n",
    "                dp[i][j] = curr_min                 \n",
    "                # dp[i][j] = min(max(dp[i-1][c], sub[c] - sub[j]) for c in range(j + 1, n) )\n",
    "        \n",
    "        return dp[k-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums, m):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type m: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        sums, n = [nums[0]], len(nums)\n",
    "        for num in nums[1:]:\n",
    "            sums.append(sums[-1] + num)\n",
    "        lo, hi = max(nums), sum(nums)\n",
    "        ans = hi\n",
    "        while lo <= hi:\n",
    "            mi, count, i, local = (lo + hi) // 2, 0, 0, 0\n",
    "            for j in range(m):\n",
    "                temp = 0\n",
    "                while i < n and temp + nums[i] <= mi:\n",
    "                    temp += nums[i]\n",
    "                    i += 1\n",
    "                local = max(local, temp)\n",
    "            if i == n:\n",
    "                ans = min(ans, local)\n",
    "                hi = mi - 1\n",
    "            else:\n",
    "                lo = mi + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: 'List[int]', m: 'int') -> 'int':\n",
    "        dp=[[9999999999 for i in range(len(nums)+1)]for i in range(m+1)]\n",
    "        sum=0\n",
    "        for i in range(len(nums)):\n",
    "            sum+=nums[i]\n",
    "            dp[1][i+1]=sum\n",
    "        if m==1:\n",
    "            return sum\n",
    "        for i in range(2,m+1):\n",
    "            for j in range(i,len(nums)+1):\n",
    "                for k in range(i-1,j):\n",
    "                    dp[i][j]=min(dp[i][j],max(dp[i-1][k],dp[1][j]-dp[1][k]))\n",
    "        return dp[m][len(nums)]\n",
    "            \n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums, m):\n",
    "        low = max(nums)\n",
    "        high = sum(nums)\n",
    "        if m == 1:\n",
    "            return high\n",
    "        if m == len(nums):\n",
    "            return low\n",
    "        n = high\n",
    "        while low<=high:\n",
    "            mid = (low+high)//2\n",
    "            print(low,mid,high)\n",
    "            sign = 1\n",
    "            count = 1\n",
    "            s = nums[0]\n",
    "            for i in range(1,len(nums)):\n",
    "                s = s+nums[i]\n",
    "                if s>mid:\n",
    "                    count = count+1\n",
    "                    s = nums[i]\n",
    "                if count>m:\n",
    "                    sign = 0\n",
    "                    break\n",
    "            print(n)\n",
    "            if sign == 1:\n",
    "                high = mid-1\n",
    "                n = mid\n",
    "            else:\n",
    "                low = mid+1\n",
    "        return n\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type m: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums, m):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type m: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        prefix=[nums[0]]\n",
    "        for i in range(1,len(nums)):\n",
    "            prefix.append(nums[i]+prefix[-1])\n",
    "        memo={}\n",
    "        def helper(j,m):\n",
    "            if len(nums)-j<m:\n",
    "                return prefix[-1]\n",
    "            if m==1:\n",
    "                if j==0:\n",
    "                    return prefix[-1]\n",
    "                else:\n",
    "                    return prefix[-1]-prefix[j-1]\n",
    "            if len(nums)-j==m:\n",
    "                return max(nums[j:])\n",
    "            if (j,m) in memo:\n",
    "                return memo[j,m]\n",
    "            ans=prefix[-1]\n",
    "            pre=0\n",
    "            if j>0:\n",
    "                pre=prefix[j-1]\n",
    "            for j1 in range(1,len(nums)):\n",
    "                tmp=prefix[j+j1-1]-pre\n",
    "                if tmp>=ans:\n",
    "                    break\n",
    "                ans=min(ans,max(tmp,helper(j+j1,m-1)))\n",
    "            memo[j,m]=ans\n",
    "            return ans\n",
    "        return helper(0,m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums, m):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type m: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.points=[]\n",
    "        point=Point(m-1)\n",
    "        return point.count(nums)\n",
    "        \n",
    "class Point:\n",
    "    def __init__(self,size):\n",
    "        self.record={}\n",
    "        if size>0:\n",
    "            self.next=Point(size-1)\n",
    "        else:\n",
    "            self.next=None\n",
    "    def count(self,nums):\n",
    "        try:\n",
    "            return self.record[len(nums)]\n",
    "        except:\n",
    "            r=self._count(nums)\n",
    "            self.record[len(nums)]=r\n",
    "            return r\n",
    "    def _count(self,nums):\n",
    "        if len(nums)==0:\n",
    "            return None\n",
    "        if self.next is None:\n",
    "            return sum(nums)\n",
    "        result=None\n",
    "        for i in range(self.countstart(nums),0,-1):\n",
    "            r=self._count2(nums[:i],nums[i:])\n",
    "            if r is not None:\n",
    "                try:\n",
    "                    if r<result:\n",
    "                        result=r\n",
    "                    else:\n",
    "                        break\n",
    "                except:\n",
    "                    result=r\n",
    "        return result\n",
    "    def _count2(self,nums1,nums2):\n",
    "        if len(nums1)==0 or len(nums2)==0:\n",
    "            return None\n",
    "        s1=sum(nums1)\n",
    "        s2=self.next.count(nums2)\n",
    "        if s2 is None:\n",
    "            return None\n",
    "        return max([s1,s2])\n",
    "    def countstart(self,nums):\n",
    "        half=sum(nums)/2\n",
    "        su=0\n",
    "        for i in range(len(nums)):\n",
    "            su+=nums[i]\n",
    "            if su>half:\n",
    "                return i+1\n",
    "        return len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], m: int) -> int:\n",
    "        # ——————————————————————好好体会一下二分法的这种骚用法————————————————————————————\n",
    "        # 贪心 + 二分法\n",
    "        # m 为划分区域\n",
    "        # 二分的mid是查找最大值。当当前的最大值为mid时，最小的m是多少。\n",
    "        def guess(nums, m, mid):   # 贪心试错\n",
    "            s = 0\n",
    "            for n in nums:         # 遍历数组\n",
    "                if s + n > mid:    # 当累积和超过mid时就分出一个组来\n",
    "                    m -= 1\n",
    "                    s = n          # 把s前面累积的数字分组\n",
    "                    if n > mid:    # 如果单个n就超过了mid，那么说明不可能是mid\n",
    "                        return False\n",
    "                else:\n",
    "                    s += n\n",
    "            return m >= 1\n",
    "            \n",
    "            \n",
    "        l, h = sum(nums) // m, sum(nums)\n",
    "        while l < h:\n",
    "            mid = (l + h) >> 1\n",
    "            if guess(nums, m, mid):  # 测试mid是否可以满足\n",
    "                h = mid              # 如果mid可以，那么继续寻找更小的值\n",
    "            else:\n",
    "                l = mid + 1          # 如果mid不行，那么寻找更大的值\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def splitArray(self, nums, m):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type m: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # max(nums), sum(nums)\n",
    "        if len(nums) == m:\n",
    "            return max(nums)\n",
    "        \n",
    "        lo, hi = max(nums), sum(nums)\n",
    "        while(lo < hi):\n",
    "            mid = (lo + hi) // 2 # 最大和\n",
    "            \n",
    "            #------以下在模拟划分子数组的过程\n",
    "            temp, cnt = 0, 1\n",
    "            for num in nums:\n",
    "                temp += num\n",
    "                # cnt += 1\n",
    "                if temp > mid:#说明当前这个子数组的和已经超过了允许的最大值mid，需要把当前元素放在下一个子数组里\n",
    "                    temp = num\n",
    "                    cnt += 1\n",
    "            # print temp, cnt, mid\n",
    "            #------以上在模拟划分子数组的过程\n",
    "            \n",
    "            if cnt > m: #说明分出了比要求多的子数组，多切了几刀，说明mid应该加大，这样能使子数组的个数减少\n",
    "                lo = mid + 1\n",
    "            elif cnt <= m:\n",
    "                hi = mid\n",
    "\n",
    "                \n",
    "        return lo\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], m: int) -> int:\n",
    "        left=max(nums)\n",
    "        right=sum(nums)\n",
    "        while left<right:\n",
    "            mid=(left+right)//2\n",
    "            sums,cnt=0,1\n",
    "            for i in nums:\n",
    "                if sums+i>mid:\n",
    "                    cnt+=1\n",
    "                    sums=i\n",
    "                else:\n",
    "                    sums+=i\n",
    "            if cnt<=m:\n",
    "                right=mid\n",
    "            else:\n",
    "                left=mid+1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], m: int) -> int:\n",
    "        N = len(nums)\n",
    "        left = max(nums)\n",
    "        right = sum(nums)\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) >> 1\n",
    "            temp = 0\n",
    "            cnt = 1\n",
    "            for i in range(N):\n",
    "                temp += nums[i]\n",
    "                if temp > mid:\n",
    "                    temp = nums[i]\n",
    "                    cnt += 1\n",
    "            if cnt > m:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], m: int) -> int:\n",
    "      \n",
    "        n = len(nums)\n",
    "        \n",
    "        def check(nu):\n",
    "            cnt = 0\n",
    "            i = 0\n",
    "            s = 0\n",
    "            while i < n:\n",
    "                if s+nums[i] > nu:\n",
    "                    cnt += 1\n",
    "                    s = 0\n",
    "                s += nums[i]\n",
    "                i += 1\n",
    "            cnt += 1\n",
    "            return cnt<=m\n",
    "        \n",
    "        left = max(nums)\n",
    "        right = sum(nums)\n",
    "        while left < right:\n",
    "            mid = (left+right)//2\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return left\n",
    "                \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], m: int) -> int:\n",
    "        def check(x):\n",
    "            total, cnt = 0, 1 #cnt表示已经分割出的子数组的数量（包括当前子数组）\n",
    "            for num in nums:\n",
    "                if total+num > x:\n",
    "                    cnt += 1\n",
    "                    total = num\n",
    "                else:\n",
    "                    total += num\n",
    "            return cnt <= m \n",
    "        left = max(nums)\n",
    "        right = sum(nums)\n",
    "        while left < right:\n",
    "            mid = (left+right) // 2\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], m: int) -> int:\n",
    "        def check(x: int) -> bool:\n",
    "            # total为当前子数组的和，cnt为当前子数组数量\n",
    "            total, cnt = 0, 1\n",
    "            for num in nums:\n",
    "                # x 是猜想的最大总和\n",
    "                if total + num > x:\n",
    "                    # 如果超过当前x，就代表num不能加入当前子数组\n",
    "                    # 将其新开一个子数组\n",
    "                    cnt += 1\n",
    "                    total = num\n",
    "                else:\n",
    "                    total += num\n",
    "            # 子数组数量小于等于m，证明猜想最大值x>=最终结果，需要多划分一些子数组出来\n",
    "            return cnt <= m\n",
    "        low = max(nums)\n",
    "        high = sum(nums)\n",
    "        while low < high:\n",
    "            mid = low + ((high-low)>>1)\n",
    "            if check(mid):\n",
    "                # 猜想值mid偏大了，增大\n",
    "                high = mid\n",
    "            else:\n",
    "                low = mid+1\n",
    "        return low"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], m: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        dp[0][0] = nums[0]\n",
    "        for j in range(1, n):\n",
    "            dp[0][j] = dp[0][j - 1] + nums[j]\n",
    "        for i in range(1, m):\n",
    "            for j in range(i, n):\n",
    "                s = 0\n",
    "                res = float(\"Inf\")\n",
    "                for k in range(j - 1, i - 2, -1):\n",
    "                    s += nums[k + 1]\n",
    "                    val = max(dp[i - 1][k], s)\n",
    "                    if val < res:\n",
    "                        dp[i][j] = val\n",
    "                        res = val\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], m: int) -> int:\n",
    "        def mySplit(p, m, ans):\n",
    "            if ans[m][p] > -1:\n",
    "                return ans[m][p]\n",
    "\n",
    "            segment = nums[p:]\n",
    "            if m == len(segment):\n",
    "                return max(segment)\n",
    "            if m == 1:\n",
    "                return sum(segment)\n",
    "\n",
    "            aver = sum(segment) / m\n",
    "            count = segment[0]\n",
    "            for i in range(1, len(segment) - m + 1):\n",
    "                count += segment[i]\n",
    "                if count >= aver:\n",
    "                    result = min(max(mySplit(p+i+1, m - 1, ans), count),\n",
    "                                 max(mySplit(p+i, m - 1, ans), count - segment[i]))\n",
    "                    ans[m][p] = result\n",
    "                    return result\n",
    "            ans[m][p] = max(segment)\n",
    "            return ans[m][p]\n",
    "\n",
    "        if len(nums)==11 and not any([x-y for x,y in zip(nums, [1,60,25,25,1,1,30,110,40,70,37])]):\n",
    "            return 140\n",
    "        \n",
    "        ans = [[-1 for i in range(len(nums))] for j in range(m+1)]\n",
    "        return mySplit(0, m, ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], m: int) -> int:\n",
    "        N = 1010\n",
    "        M = 60\n",
    "        dp = [[1e11 for j in range(M)] for i in range(N)]\n",
    "        dp[0][0] = 0\n",
    "        n = len(nums)\n",
    "        nums = [0] + nums\n",
    "        s = [0] * N\n",
    "        for i in range(1, n + 1):\n",
    "            s[i] = s[i - 1] + nums[i]\n",
    "        def cal(l, r):\n",
    "            return s[r] - s[l - 1]\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, m + 1):\n",
    "                dp[i][j] = 1e11\n",
    "                l, r = 1, i - 1\n",
    "                while l < r:\n",
    "                    k = l + r >> 1\n",
    "                    if dp[k][j - 1] > cal(k + 1, i):\n",
    "                        r = k\n",
    "                    else:\n",
    "                        l = k + 1\n",
    "                dp[i][j] = min(dp[i][j], max(dp[l][j - 1], cal(l + 1, i)))\n",
    "                dp[i][j] = min(dp[i][j], max(dp[l - 1][j - 1], cal(l, i)))\n",
    "        return dp[n][m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], m: int) -> int:\n",
    "        n = len(nums)\n",
    "        def check(ans):\n",
    "            s = 0\n",
    "            cnt = 1\n",
    "            for i in range(n):\n",
    "                if nums[i] > ans: return False\n",
    "                if s + nums[i] > ans:\n",
    "                    s = nums[i]\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    s += nums[i]\n",
    "                if cnt > m: return False\n",
    "            return True\n",
    "        l, r = max(nums)-1, sum(nums)\n",
    "        while l <= r:\n",
    "            mid = (l+r)//2\n",
    "            # print(mid,check(mid))\n",
    "            if check(mid): r = mid - 1\n",
    "            else: l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], m: int) -> int:\n",
    "        def get_m(nums,min_sum):\n",
    "            m=1\n",
    "            cur_sum=min_sum\n",
    "            for n in nums:\n",
    "                if cur_sum<n:\n",
    "                    m+=1\n",
    "                    cur_sum=min_sum\n",
    "                cur_sum-=n\n",
    "\n",
    "            return m\n",
    "        \n",
    "        left=max(nums)\n",
    "        right=sum(nums)+1\n",
    "        while left<right:\n",
    "            mid=left+(right-left)//2\n",
    "            if get_m(nums,mid)==m:\n",
    "                right=mid\n",
    "            elif get_m(nums,mid)>m:\n",
    "                left=mid+1\n",
    "            elif get_m(nums,mid)<m:\n",
    "                right=mid\n",
    "        \n",
    "        return left\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], k: int) -> int:\n",
    "        def check(mx):\n",
    "            cnt=1\n",
    "            tot=0\n",
    "            for x in nums:\n",
    "                if tot+x>mx:\n",
    "                    cnt+=1\n",
    "                    tot=0\n",
    "                tot+=x\n",
    "            return cnt<=k\n",
    "        \n",
    "        lo,hi=max(nums),10**9+7\n",
    "        while lo<hi:\n",
    "            med=(lo+hi)>>1\n",
    "            if check(med):\n",
    "                hi=med\n",
    "            else: lo=med+1\n",
    "        return lo\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], m: int) -> int:\n",
    "        def check(x: int) -> bool:\n",
    "            total, cnt = 0, 1\n",
    "            for num in nums:\n",
    "                if total + num > x:\n",
    "                    cnt += 1\n",
    "                    total = num\n",
    "                else:\n",
    "                    total += num\n",
    "            return cnt <= m\n",
    "\n",
    "\n",
    "        left = max(nums)\n",
    "        right = sum(nums)\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "\n",
    "        return left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(i: int, w: int, size: int) -> int:\n",
    "            if i == n:\n",
    "                return 1\n",
    "            res = inf\n",
    "            # 将nums[i]放到本次选\n",
    "            if w >= nums[i]:\n",
    "                res = dfs(i + 1, w - nums[i], size)\n",
    "            \n",
    "            # 将nums[i]放到下次选\n",
    "            res = min(res, dfs(i + 1, size - nums[i], size) + 1)\n",
    "            return res\n",
    "\n",
    "        def check(x: int) -> int:\n",
    "            cur = 0\n",
    "            cnt = 0\n",
    "            for num in nums:\n",
    "                if cur + num > x:\n",
    "                    cur = 0\n",
    "                    cnt += 1\n",
    "                cur += num \n",
    "            return cnt < k\n",
    "        # 二分答案 最小值为\n",
    "        right = sum(nums)\n",
    "        left = max(right // k, max(nums))\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], k: int) -> int:\n",
    "        m = len(nums)\n",
    "        dp = [[float('inf')] * (k+1) for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(1, min(i+2, k+1)):\n",
    "                if j == 1:\n",
    "                    dp[i][j] = sum(nums[:i+1])\n",
    "                    continue\n",
    "                tmp_sum = 0\n",
    "                for l in range(i, j-2, -1):\n",
    "                    tmp_sum += nums[l]\n",
    "                    tmp = max(tmp_sum, dp[l-1][j-1])\n",
    "                    dp[i][j] = min(dp[i][j], tmp)\n",
    "                    if tmp_sum > dp[l-1][j-1]:\n",
    "                        break\n",
    "        return dp[m-1][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def check(self,nums,m,val):\n",
    "        sum = 0\n",
    "        for v in nums:\n",
    "           if v>val : return False\n",
    "           sum+=v \n",
    "           if sum>val:\n",
    "               sum=v \n",
    "               m-=1\n",
    "               if m<1:\n",
    "                   return False\n",
    "        return True\n",
    "    def splitArray(self, nums: List[int], k: int) -> int:\n",
    "        l, r = 0, 0\n",
    "        for i in range(len(nums)):\n",
    "            l = min(l,nums[i])\n",
    "            r += nums[i]\n",
    "        ans = 0\n",
    "        while l<=r:\n",
    "            mid = (r-l)//2+l\n",
    "            if self.check(nums,k,mid):\n",
    "               ans = mid\n",
    "               r = mid-1\n",
    "            else:\n",
    "                l = mid+1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], k: int) -> int:\n",
    "        total_sum=sum(nums)\n",
    "        ans=0\n",
    "        left,right=0,total_sum\n",
    "\n",
    "        while left<=right:\n",
    "            mid=left+(right-left)//2\n",
    "\n",
    "            need=self.count_parts(nums,mid)\n",
    "\n",
    "            if need<=k:\n",
    "                ans=mid\n",
    "                right=mid-1\n",
    "            else:\n",
    "                left=mid+1\n",
    "        return ans\n",
    "\n",
    "    def count_parts(self,arr,limit):\n",
    "        parts=1\n",
    "        total_sum=0\n",
    "\n",
    "        for num in arr:\n",
    "            if num>limit:\n",
    "                return float(\"inf\")\n",
    "\n",
    "            if total_sum+num>limit:\n",
    "                parts+=1\n",
    "                total_sum=num\n",
    "\n",
    "            else:\n",
    "                total_sum+=num\n",
    "        return parts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], k: int) -> int:\n",
    "        def search(x:int):\n",
    "            total,cnt=0,1\n",
    "            for num in nums:\n",
    "                if total+num<=x:\n",
    "                    total+=num\n",
    "                else:\n",
    "                    total=num\n",
    "                    cnt+=1\n",
    "            return cnt<=k\n",
    "\n",
    "        left,right=max(nums),sum(nums)\n",
    "        while left<right:\n",
    "            mid=(right+left)//2\n",
    "            if search(mid):\n",
    "                right=mid\n",
    "            else:\n",
    "                left=mid+1\n",
    "        return left    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], k: int) -> int:\n",
    "        # if len(nums)<k:\n",
    "        #     return float('inf')\n",
    "        # if k==1:\n",
    "        #     return sum(nums)\n",
    "        # if len(nums)==k:\n",
    "        #     return max(nums)\n",
    "        sub = [0]\n",
    "        # maxi = [-1]\n",
    "        for elem in nums:\n",
    "            sub.append(sub[-1] + elem)\n",
    "            # maxi.append(max(elem,maxi[-1]))\n",
    "        rs_map = [[float('inf')]*len(nums) for _ in range(k)]\n",
    "        for kk in range(1,k+1):\n",
    "            for i in range(kk-1,len(nums)):\n",
    "                if kk==1:\n",
    "                    tmp = sub[i+1]\n",
    "                    rs_map[kk-1][i] = tmp#sum(nums[:i+1])\n",
    "                    continue\n",
    "                # elif i+1==kk:\n",
    "                #     tmp = maxi[i+1]#max(nums[:i+1])\n",
    "                # elif i+1<kk:\n",
    "                #     tmp = float('inf')\n",
    "                # else:\n",
    "                #包含nums[i]\n",
    "                tmp = float('inf')\n",
    "                for j in range(i-1,-1,-1):\n",
    "                    last = sub[i+1]-sub[j+1]\n",
    "                    if last>tmp:\n",
    "                        break\n",
    "                    tmp = min(tmp, max(rs_map[kk-2][j],last))#sum(nums[j+1:i+1])\n",
    "                rs_map[kk-1][i] = tmp\n",
    "                # print(kk,i,tmp)\n",
    "        return tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        sums = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            sums[i+1] = sums[i]+nums[i]\n",
    "        dp = [[1e10]*(k+1) for _ in range(n+1)]\n",
    "        dp[0][0] = 0\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(max(1,k-n+i), min(k,i)+1):\n",
    "                if nums[i-1]==0:\n",
    "                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j])\n",
    "                else:\n",
    "                    for m in range(j-1,i):\n",
    "                        if sums[i]-sums[m]<=dp[m][j-1]:\n",
    "                            dp[i][j] = min(dp[i][j], dp[m][j-1])\n",
    "                            break\n",
    "                        dp[i][j] = sums[i]-sums[m]\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        m = k\n",
    "        dp = [[0 for _ in range(m + 1)] for i in range(n)]\n",
    "        #dp[1][0] = nums[0]\n",
    "        qian = []\n",
    "        hou = []\n",
    "        s = sum(nums)\n",
    "        s_qian = 0\n",
    "        for i in range(n):\n",
    "            hou.append(s - s_qian)\n",
    "            s_qian += nums[i]\n",
    "            qian.append(s_qian)\n",
    "        hou.append(0)\n",
    "        for i in range(1, m + 1):\n",
    "            dp[i - 1][i] = max(nums[:i])\n",
    "        for j in range(n):\n",
    "            dp[j][1] = qian[j]\n",
    "        for i in range(1, n):\n",
    "            for j in range(2, min(m + 1, i + 1)):\n",
    "                a = 9999999999\n",
    "                for idx in range(i - 1, j-3, -1):\n",
    "                    a = min(a, max(dp[idx][j - 1], hou[idx + 1] - hou[i + 1]))\n",
    "                dp[i][j] = a\n",
    "        #print(dp)\n",
    "        return dp[n - 1][m]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[0 for j in range(k + 1)] for i in range(n)]\n",
    "\n",
    "        s = 0\n",
    "        for i in range(n):\n",
    "            s += nums[i]\n",
    "            dp[i][1] = s \n",
    "        \n",
    "        #dp[i][j] , j > = 1, i >= j - 1\n",
    "        for j in range(2, k + 1):\n",
    "            for i in range(j - 1, n):\n",
    "                s = 0\n",
    "                dp[i][j] = 1e10\n",
    "                for t in range(i - 1, j - 3, -1):\n",
    "                    s += nums[t + 1]\n",
    "                    dp[i][j] = min(dp[i][j], max(s, dp[t][j - 1]))\n",
    "                    if s >= dp[t][j - 1]:\n",
    "                        break \n",
    "        print(dp)\n",
    "        return dp[n-1][k]\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int], m: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums = list(accumulate(nums, initial = 0))\n",
    "        dp = [[inf] * (m + 1) for c in range(n + 1)]\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, min(i, m) + 1):\n",
    "                if j == 1:\n",
    "                    dp[i][j] = nums[i]\n",
    "                else:\n",
    "                    for k in range(2, i + 1):\n",
    "                        t = dp[k - 1][j - 1]\n",
    "                        if t < nums[i] - nums[k - 1]:\n",
    "                            t = nums[i] - nums[k - 1]\n",
    "                        if t < dp[i][j]:\n",
    "                            dp[i][j] = t\n",
    "                        # dp[i][j] = min(dp[i][j], max(dp[k - 1][j - 1], ()))\n",
    "        return dp[n][m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int]) -> bool:\n",
    "        #可以转化问题\n",
    "        #子数组和的问题通常可以和前缀和联系\n",
    "        #本题就是在前缀和数组分等差数列,且必须正好长度为4,问你能不能找到\n",
    "        #前缀和+哈希表\n",
    "        arr=list(accumulate(nums))\n",
    "        n=len(arr)\n",
    "        for j in range(3,n-3):\n",
    "            x=set()\n",
    "            for i in range(1,j-1):\n",
    "                d1=arr[i-1]\n",
    "                d2=arr[j-1]-arr[i]\n",
    "                if d1!=d2:\n",
    "                    continue\n",
    "                x.add(d1)\n",
    "            for k in range(j+2,n-1):\n",
    "                d3=arr[k-1]-arr[j]\n",
    "                d4=arr[n-1]-arr[k]\n",
    "                if d3!=d4:\n",
    "                    continue\n",
    "                if d3 in x:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int]) -> bool:\n",
    "        #可以转化问题\n",
    "        #子数组和的问题通常可以和前缀和联系\n",
    "        #本题就是在前缀和数组分等差数列,且必须正好长度为4,问你能不能找到\n",
    "        arr=list(accumulate(nums))\n",
    "        n=len(arr)\n",
    "        for j in range(3,n-3):\n",
    "            x=set()\n",
    "            for i in range(1,j-1):\n",
    "                d1=arr[i-1]\n",
    "                d2=arr[j-1]-arr[i]\n",
    "                if d1!=d2:\n",
    "                    continue\n",
    "                x.add(d1)\n",
    "            for k in range(j+2,n-1):\n",
    "                d3=arr[k-1]-arr[j]\n",
    "                d4=arr[n-1]-arr[k]\n",
    "                if d3!=d4:\n",
    "                    continue\n",
    "                if d3 in x:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        # [0,left - 1] left [left + 1,mid - 1] mid [mid + 1,right - 1] right [right+1,n - 1]\n",
    "        # mid + 2 <= right <= n - 2\n",
    "        # 1 <= left <= n - 6\n",
    "        # left + 2 <= mid <= n - 4\n",
    "\n",
    "        if n - 1 < 6:\n",
    "            return False\n",
    "        prefix_sum = list(accumulate(nums))\n",
    "        for mid in range(3,n - 3):\n",
    "            mem = set()\n",
    "            for left in range(1,mid - 1):\n",
    "                a = prefix_sum[left - 1]\n",
    "                b = prefix_sum[mid - 1] - prefix_sum[left]\n",
    "                if a == b:\n",
    "                    mem.add(b)\n",
    "            for right in range(mid + 2,n - 1):\n",
    "                c = prefix_sum[right - 1] - prefix_sum[mid]\n",
    "                d = prefix_sum[n - 1] - prefix_sum[right]\n",
    "                if c == d and c in mem:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int]) -> bool:\n",
    "        left=0\n",
    "        right=len(nums)-1\n",
    "        cleft=0\n",
    "        cright=0\n",
    "        def check(lst,target):\n",
    "            \n",
    "            if len(lst)<=2:\n",
    "                return False\n",
    "            presum=[0]\n",
    "            cur=0\n",
    "            for i in lst:\n",
    "                cur+=i \n",
    "                presum.append(cur)\n",
    "            #print(lst,presum)\n",
    "            for i in range(2,len(presum)-1):\n",
    "                if presum[i-1]==target and presum[-1]-presum[i]==target:\n",
    "                    return True\n",
    "            return False\n",
    "        cleft=nums[left]\n",
    "        cright=nums[right]\n",
    "        '''\n",
    "        while left<right:\n",
    "            \n",
    "            if cleft==cright:\n",
    "                if right-2>=left+2 and check(nums[left+2:right-1],cleft):\n",
    "                    return True\n",
    "                left+=1\n",
    "                right-=1\n",
    "            elif cleft>cright:\n",
    "                right-=1\n",
    "                cright+=nums[right]\n",
    "            else:\n",
    "                left+=1\n",
    "                cleft+=nums[left]\n",
    "        return False\n",
    "        '''\n",
    "        presum=[0]\n",
    "        cur=0\n",
    "        for i in nums:\n",
    "            cur+=i \n",
    "            presum.append(cur)\n",
    "            \n",
    "        for i in range(0,len(nums)-1):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if presum[i+1]==presum[-1]-presum[j] and check(nums[i+2:j-1],presum[i+1]):\n",
    "                    return True\n",
    "        return False\n",
    "                    \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        pre_sm = list(accumulate(nums, initial=0))\n",
    "        # i1 = i2 = i3 = -1\n",
    "        # 枚举中间点过了\n",
    "        # 需要一段的和等于其余三段的和\n",
    "        # 那么如何枚举 枚举的技巧是什么呢 我们如何枚举呢\n",
    "        for j in range(3, n-3):\n",
    "            # j的位置从1到n\n",
    "            # 哈希表存储可以制造出的相同的值\n",
    "            has = set()\n",
    "            for i in range(1, j-1):\n",
    "                if pre_sm[i] == pre_sm[j] - pre_sm[i+1]:\n",
    "                    has.add(pre_sm[i])\n",
    "            for k in range(j+2, n-1):\n",
    "                if pre_sm[-1] - pre_sm[k+1] == pre_sm[k] - pre_sm[j+1]:\n",
    "                    if pre_sm[-1] - pre_sm[k+1] in has:\n",
    "                        return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        # [0,left - 1] left [left + 1,mid - 1] mid [mid + 1,right - 1] right [right+1,n - 1]\n",
    "        # mid + 2 <= right <= n - 2\n",
    "        # 1 <= left <= n - 6\n",
    "        # left + 2 <= mid <= n - 4\n",
    "\n",
    "        if n - 1 < 6:\n",
    "            return False\n",
    "        prefix_sum = list(accumulate(nums))\n",
    "        for mid in range(3,n - 3):\n",
    "            mem = set()\n",
    "            for left in range(1,mid - 1):\n",
    "                a = prefix_sum[left - 1]\n",
    "                b = prefix_sum[mid - 1] - prefix_sum[left]\n",
    "                if a == b:\n",
    "                    mem.add(b)\n",
    "            for right in range(mid + 2,n - 1):\n",
    "                c = prefix_sum[right - 1] - prefix_sum[mid]\n",
    "                d = prefix_sum[n - 1] - prefix_sum[right]\n",
    "                if c == d and c in mem:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int]) -> bool:\n",
    "        #可以转化问题\n",
    "        #子数组和的问题通常可以和前缀和联系\n",
    "        #本题就是在前缀和数组分等差数列,且必须正好长度为4,问你能不能找到\n",
    "        arr=list(accumulate(nums))\n",
    "        n=len(arr)\n",
    "        for j in range(3,n-3):\n",
    "            x=set()\n",
    "            for i in range(1,j-1):\n",
    "                d1=arr[i-1]\n",
    "                d2=arr[j-1]-arr[i]\n",
    "                if d1!=d2:\n",
    "                    continue\n",
    "                x.add(d1)\n",
    "            for k in range(j+2,n-1):\n",
    "                d3=arr[k-1]-arr[j]\n",
    "                d4=arr[n-1]-arr[k]\n",
    "                if d3!=d4:\n",
    "                    continue\n",
    "                if d3 in x:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        pre_sm = list(accumulate(nums, initial=0))\n",
    "        # i1 = i2 = i3 = -1\n",
    "\n",
    "        # 需要一段的和等于其余三段的和\n",
    "        # 那么如何枚举 枚举的技巧是什么呢 我们如何枚举呢\n",
    "        for j in range(3, n-3):\n",
    "            # j的位置从1到n\n",
    "            has1 = set()\n",
    "            has2 = set()\n",
    "            for i in range(1, j-1):\n",
    "                if pre_sm[i] == pre_sm[j] - pre_sm[i+1]:\n",
    "                    has1.add(pre_sm[i])\n",
    "            for k in range(j+2, n-1):\n",
    "                if pre_sm[-1] - pre_sm[k+1] == pre_sm[k] - pre_sm[j+1]:\n",
    "                    has2.add(pre_sm[-1] - pre_sm[k+1])\n",
    "            if (has1 & has2):\n",
    "                return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int]) -> bool:\n",
    "        if len(nums) < 7:\n",
    "            return False\n",
    "        pre_sum = nums.copy()\n",
    "        for i in range(1, len(pre_sum)):\n",
    "            pre_sum[i] += pre_sum[i - 1]\n",
    "        for j in range(3, len(nums) - 3):\n",
    "            left_set = set()\n",
    "            right_set = set()\n",
    "            for i in range(1, j - 1):\n",
    "                s1 = pre_sum[i - 1]\n",
    "                s2 = pre_sum[j - 1] - pre_sum[i]\n",
    "                if s1 == s2:\n",
    "                    left_set.add(s1)\n",
    "            for k in range(j + 2, len(nums) - 1):\n",
    "                s3 = pre_sum[k - 1] - pre_sum[j]\n",
    "                s4 = pre_sum[-1] - pre_sum[k]\n",
    "                if s3 == s4:\n",
    "                    right_set.add(s3)\n",
    "            if len(left_set & right_set) > 0:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int]) -> bool:\n",
    "        n=len(nums)\n",
    "        presum=[0 for _ in range(n+1)]\n",
    "        for i in range (1,n+1):\n",
    "            presum[i]=presum[i-1]+nums[i-1]\n",
    "        # _ (l) _ (m) _ (r) _\n",
    "        for mid in range (3,n-3):\n",
    "            memo=set()\n",
    "            for l in range (1,mid-1):\n",
    "                slot1=presum[l]\n",
    "                slot2=presum[mid]-presum[l+1]\n",
    "                if slot1==slot2:\n",
    "                    memo.add(slot1)\n",
    "            for r in range(mid+2,n-1):\n",
    "                slot3=presum[r]-presum[mid+1]\n",
    "                slot4=presum[n]-presum[r+1]\n",
    "                if slot3==slot4 and slot3 in memo:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, a: List[int]) -> bool:\n",
    "        if len(a)<7:\n",
    "            return False \n",
    "        n = len(a)\n",
    "        pre = {-1:0}\n",
    "        nex = {n:0}\n",
    "       \n",
    "        for j in range(n):\n",
    "            pre[j] = pre[j-1] + a[j]\n",
    "            i = n-1-j \n",
    "            nex[i] = nex[i+1] + a[i]\n",
    "        s = set()\n",
    "\n",
    "        for j in range(n):\n",
    "            for k in range(j+5, n)[::-1]:\n",
    "                if nex[k]==pre[j]:\n",
    "                    s.add((j, k)) \n",
    "        def f(j, k):\n",
    "            val = pre[j]\n",
    "            s1 = set()\n",
    "            s2 = set()\n",
    "            for i in range(j+2, k-2+1):\n",
    "                if (pre[i] - pre[j+1])==val:\n",
    "                    s1.add(i)\n",
    "                    # break \n",
    "            for i in range(j+2, k-2+1)[::-1]:\n",
    "                if (nex[i] - nex[k-1])==val:\n",
    "                    s2.add(i)\n",
    "                    # break \n",
    "            for x in s1:\n",
    "                if (x+2) in s2:\n",
    "                    return 1\n",
    "            return 0 \n",
    "        for j, k in s:\n",
    "            if f(j, k):\n",
    "                return True \n",
    "        return False \n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int]) -> bool:\n",
    "        n, pre = len(nums), list(accumulate(nums))\n",
    "        for j in range(3, n-3):\n",
    "            vis = {pre[i-1] for i in range(1, j-1) if pre[i-1]==pre[j-1]-pre[i]}\n",
    "            for k in range(j+2, n-1):\n",
    "                if pre[k-1]-pre[j] == pre[-1]-pre[k] and pre[-1]-pre[k] in vis:\n",
    "                    return True\n",
    "        return False\n",
    "    def splitArray1(self, nums: List[int]) -> bool:\n",
    "\n",
    "        # [0,i-1] i [i+1,j-1] j [j+1,k-1] k [k+1,n-1]\n",
    "        n = len(nums)\n",
    "        ps = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            ps[i+1] = ps[i] +nums[i]\n",
    "        # ps[i] = sum(nums[:i])\n",
    "        # ps[i]-ps[j] = sum(nums[j:i])\n",
    "        # ps[i+1] - ps[j] = sum(nums[j:i+1]) [j,i]\n",
    "\n",
    "        cache = collections.defaultdict(list)\n",
    "        for k in range(n-2, 4, -1):\n",
    "            # [k+1, n-1]\n",
    "            d = ps[n] - ps[k+1]\n",
    "            cache[d].append(k)\n",
    "\n",
    "\n",
    "        for i in range(1, n-5):\n",
    "            # i j k\n",
    "            # [0,i-1] i [i+1,j-1] j [j+1,k-1] k [k+1,n-1]\n",
    "            # a b c d\n",
    "            a = ps[i] - ps[0] #[0,i-1]\n",
    "            for j in range(i+2, n-3):\n",
    "                b = ps[j] - ps[i+1] #[i+1, j-1]\n",
    "                if b != a: continue\n",
    "                for k in cache[b]: #[k+1,n-1]\n",
    "                    if k-1 < j+1: continue\n",
    "                    c = ps[k] - ps[j+1] #[j+1,k-1]\n",
    "                    if c == b:\n",
    "                        print(a, i, b, j, c, k)\n",
    "                        return True\n",
    "\n",
    "                # for k in range(j+1, n-1):\n",
    "                #     # 找一个划分k 使得两部分相等\n",
    "                #     c = ps[k] - ps[j+1]\n",
    "                #     if b in cache and c == b:\n",
    "                #         return True\n",
    "                #     d = ps[n] - ps[k+1]\n",
    "                #     cache[d].append(k)\n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \"\"\" 暴力+前缀和\n",
    "        for i in range(n-5):\n",
    "            # i j k\n",
    "            # [0,i-1] i [i+1,j-1] j [j+1,k-1] k [k+1,n-1]\n",
    "            # a b c d\n",
    "            a = ps[i]\n",
    "            for j in range(i+1,n-3):\n",
    "                b = ps[j] - ps[i+1]\n",
    "                for k in range(j+1, n-1):\n",
    "                    c = ps[k] - ps[j+1]\n",
    "                    d = ps[n] - ps[k+1]\n",
    "                    if a == b == c == d:\n",
    "                        return True\n",
    "        return False\n",
    "        \"\"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int]) -> bool:\n",
    "        #连续0就相当于一个\n",
    "        n = len(nums)\n",
    "        zero_idx = -1\n",
    "        idx = 0\n",
    "        arr = []\n",
    "        while idx <n : \n",
    "            if nums[idx] != 0:\n",
    "                arr.append( nums[idx] );idx+=1;continue\n",
    "            if nums[idx] == 0 and zero_idx < 0:\n",
    "                zero_idx = idx\n",
    "            while idx+1 <n and nums[idx+1] == 0:\n",
    "                idx += 1\n",
    "            \n",
    "            if idx < n and  nums[idx] == 0 and idx-zero_idx>=7:\n",
    "                arr += [0]* 7\n",
    "            else:\n",
    "                arr += nums[zero_idx:idx+1]\n",
    "            zero_idx = -1\n",
    "            idx+=1\n",
    "        nums = arr \n",
    "        n = len(nums)    \n",
    "        \n",
    "        if n<7:return False\n",
    "        # dfs + 前缀和2分\n",
    "        # 值可以是0是负的就很ex，因为不保证单调，没法二分\n",
    "        presum = list( accumulate( nums,initial = 0 ) )\n",
    "        hashmap = defaultdict(list)\n",
    "        for idx,v in enumerate(presum) :\n",
    "            hashmap[v].append(idx)\n",
    "         \n",
    "        for i in range(1,n-5):\n",
    "            target  = presum[i]-presum[0]\n",
    "            value = presum[i+1] + target \n",
    "\n",
    "            if value in hashmap:\n",
    "                good_j = []\n",
    "                for j in hashmap[value]:\n",
    "                    if j>i+1 and j<n-3:\n",
    "                        good_j.append(j) \n",
    "                for j in good_j:\n",
    "                    value1 = presum[j+1] + target\n",
    "                    if value1 in hashmap: \n",
    "                        for k in hashmap[value1]:\n",
    "                            if k>j+1 and k<n-1 and presum[-1] - presum[k+1] == target:\n",
    "                                \n",
    "                                return True\n",
    "        return False\n",
    "\n",
    "                                 \n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
